unit AVGenerics;

interface
uses Generics.Collections, SysUtils, RTLConsts;

type

  TAVQueue<T> = class(TEnumerable<T>)
  public
    type PItem = ^T;
  private
    FHead: Integer;
    FTail: Integer;
    FCount: Integer;
    FItems: array of T;
    FOnNotify: TCollectionNotifyEvent<T>;
    FArrayManager: TArrayManager<T>;
    procedure Grow;
    procedure SetCapacity(Value: Integer);
    function DoDequeue(Notification: TCollectionNotification): T;
    procedure DoSetCapacity(Value: Integer);
    function GetCapacity: Integer;
    function GetItem(index: integer): T;
    procedure SetItem(index: integer; value: T);
    function GetPItem(index: integer): PItem;
  protected
    function DoGetEnumerator: TEnumerator<T>; override;
    procedure Notify(const Item: T; Action: TCollectionNotification); virtual;
  public
    constructor Create; overload;
    constructor Create(Collection: TEnumerable<T>); overload;
    destructor Destroy; override;
    procedure Enqueue(const Value: T);
    function Dequeue: T;
    function Extract: T;
    function Peek: T;
    procedure Clear;
    procedure TrimExcess;
    property Count: Integer read FCount;
    property Capacity: Integer read GetCapacity write DoSetCapacity;
    property OnNotify: TCollectionNotifyEvent<T> read FOnNotify write FOnNotify;
    function ToArray: TArray<T>; override; final;

    property Items[index: integer]: T read GetItem write SetItem;
    property PItems[index: integer]: PItem read GetPItem;

    type
      TEnumerator = class(TEnumerator<T>)
      private
        FQueue: TAVQueue<T>;
        FIndex: Integer;
        function GetCurrent: T;
      protected
        function DoGetCurrent: T; override;
        function DoMoveNext: Boolean; override;
      public
        constructor Create(AQueue: TAVQueue<T>);
        property Current: T read GetCurrent;
        function MoveNext: Boolean;
      end;

    function GetEnumerator: TEnumerator; reintroduce;
  end;

  TAVArray<T> = record
  private
    fArray: TArray<T>;
    function GetCount: integer;
    procedure SetCount(value: integer);
    function GetItem(index: integer): T;
    procedure SetItem(index: integer; value: T);
  public
    function Add(value: T): integer;

    property Arr: TArray<T> read fArray;
    property Count: integer read GetCount write SetCount;
    property Items[index: integer]: T read GetItem write SetItem; default;
  end;

implementation


{ TQueue<T> }

procedure TAVQueue<T>.Notify(const Item: T; Action: TCollectionNotification);
begin
  if Assigned(FOnNotify) then
    FOnNotify(Self, Item, Action);
end;

constructor TAVQueue<T>.Create;
begin
  inherited Create;
{$IF Defined(WEAKREF)}
  if HasWeakRef then
    FArrayManager := TManualArrayManager<T>.Create
  else
{$ENDIF}
    FArrayManager := TMoveArrayManager<T>.Create;
end;

function TAVQueue<T>.Dequeue: T;
begin
  Result := DoDequeue(cnRemoved);
end;

destructor TAVQueue<T>.Destroy;
begin
  Clear;
  FArrayManager.Free;
  inherited;
end;

function TAVQueue<T>.DoGetEnumerator: TEnumerator<T>;
begin
  Result := GetEnumerator;
end;

procedure TAVQueue<T>.DoSetCapacity(Value: Integer);
begin
  if Value < Count then
    raise EArgumentOutOfRangeException.CreateRes(@SArgumentOutOfRange);
  SetCapacity(Value);
end;

procedure TAVQueue<T>.Enqueue(const Value: T);
begin
  if Count = Length(FItems) then
    Grow;
  FItems[FHead] := Value;
  FHead := (FHead + 1) mod Length(FItems);
  Inc(FCount);
  Notify(Value, cnAdded);
end;

function TAVQueue<T>.Extract: T;
begin
  Result := DoDequeue(cnExtracted);
end;

constructor TAVQueue<T>.Create(Collection: TEnumerable<T>);
var
  item: T;
begin
  inherited Create;
{$IF Defined(WEAKREF)}
  if HasWeakRef then
    FArrayManager := TManualArrayManager<T>.Create
  else
{$ENDIF}
    FArrayManager := TMoveArrayManager<T>.Create;
  for item in Collection do
    Enqueue(item);
end;

function TAVQueue<T>.DoDequeue(Notification: TCollectionNotification): T;
begin
  if Count = 0 then
    raise EListError.CreateRes(@SUnbalancedOperation);
  Result := FItems[FTail];
  FItems[FTail] := Default(T);
  FTail := (FTail + 1) mod Length(FItems);
  Dec(FCount);
  Notify(Result, Notification);
end;

function TAVQueue<T>.Peek: T;
begin
  if Count = 0 then
    raise EListError.CreateRes(@SUnbalancedOperation);
  Result := FItems[FTail];
end;

procedure TAVQueue<T>.Clear;
begin
  while Count > 0 do
    Dequeue;
  FHead := 0;
  FTail := 0;
  FCount := 0;
end;

function TAVQueue<T>.ToArray: TArray<T>;
begin
  Result := ToArrayImpl(Count);
end;

procedure TAVQueue<T>.TrimExcess;
begin
  SetCapacity(Count);
end;

procedure TAVQueue<T>.SetCapacity(Value: Integer);
var
  tailCount, offset: Integer;
begin
  offset := Value - Length(FItems);
  if offset = 0 then
    Exit;

  // If head <= tail, then part of the queue wraps around
  // the end of the array; don't introduce a gap in the queue.
  if (FHead < FTail) or ((FHead = FTail) and (Count > 0)) then
    tailCount := Length(FItems) - FTail
  else
    tailCount := 0;

  if offset > 0 then
    SetLength(FItems, Value);
  if tailCount > 0 then
  begin
    FArrayManager.Move(FItems, FTail, FTail + offset, tailCount);
    if offset > 0 then
      FArrayManager.Finalize(FItems, FTail, offset)
    else if offset < 0 then
      FArrayManager.Finalize(FItems, Count, (- offset));
    Inc(FTail, offset);
  end
  else if FTail > 0 then
  begin
    if Count > 0 then
    begin
      FArrayManager.Move(FItems, FTail, 0, Count);
      FArrayManager.Finalize(FItems, FCount, FTail);
    end;
    Dec(FHead, FTail);
    FTail := 0;
  end;
  if offset < 0 then
    SetLength(FItems, Value);
end;

procedure TAVQueue<T>.Grow;
var
  newCap: Integer;
begin
  newCap := Length(FItems) * 2;
  if newCap = 0 then
    newCap := 4
  else if newCap < 0 then
    OutOfMemoryError;
  SetCapacity(newCap);
end;

function TAVQueue<T>.GetCapacity: Integer;
begin
  Result := Length(FItems);
end;

function TAVQueue<T>.GetEnumerator: TEnumerator;
begin
  Result := TEnumerator.Create(Self);
end;

function TAVQueue<T>.GetItem(index: integer): T;
begin
  Result := FItems[(FTail + index) mod Length(FItems)];
end;

procedure TAVQueue<T>.SetItem(index: integer; value: T);
begin
  FItems[(FTail + index) mod Length(FItems)] := value;
end;

function TAVQueue<T>.GetPItem(index: integer): PItem;
begin
  Result := @FItems[(FTail + index) mod Length(FItems)];
end;

{ TQueue<T>.TEnumerator }

constructor TAVQueue<T>.TEnumerator.Create(AQueue: TAVQueue<T>);
begin
  inherited Create;
  FQueue := AQueue;
  FIndex := -1;
end;

function TAVQueue<T>.TEnumerator.DoGetCurrent: T;
begin
  Result := GetCurrent;
end;

function TAVQueue<T>.TEnumerator.DoMoveNext: Boolean;
begin
  Result := MoveNext;
end;

function TAVQueue<T>.TEnumerator.GetCurrent: T;
begin
  Result := FQueue.FItems[(FQueue.FTail + FIndex) mod Length(FQueue.FItems)];
end;

function TAVQueue<T>.TEnumerator.MoveNext: Boolean;
begin
  if FIndex >= FQueue.Count then
    Exit(False);
  Inc(FIndex);
  Result := FIndex < FQueue.Count;
end;

//TAVArray<T>

function TAVArray<T>.GetCount: integer;
begin
  Result := Length(fArray);
end;

procedure TAVArray<T>.SetCount(value: integer);
begin
  SetLength(fArray, value);
end;

function TAVArray<T>.GetItem(index: integer): T;
begin
  Result := fArray[index];
end;

procedure TAVArray<T>.SetItem(index: integer; value: T);
begin
  fArray[index] := value;
end;

function TAVArray<T>.Add(value: T): integer;
var n: integer;
begin
  n := length(fArray);
  SetLength(fArray, n + 1);
  fArray[n] := value;
  Result := n;
end;

end.
